#!/usr/bin/env python2
# -*- coding: utf-8 -*-

from __future__ import print_function
import random
import re


G_debug = 0

def dfa_multiples_old(n):
    """
    Takes integer n and constructs a DFA that
    matches any mutiple of n in binary.
    """
    d = [{} for i in range(n + 3)]
    d[n]['0'] = n + 1
    d[n]['1'] = 1 % n # case when n == 1
    d[n + 1]['0'] = n + 2
    d[n + 1]['1'] = n + 2
    d[n + 2]['0'] = n + 2
    d[n + 2]['1'] = n + 2
    for i in range(n):
        for c in ['0', '1']:
            d[i][c] = (i * 2 + int(c, 2)) % n # magic happens here
    return d

def multiples(n):
    """
    Takes integer 'n' and returns a regular expression matching
    any binary string that represents a multiple of 'n'.
    """
    import itertools

    def _replace_path(gnfa, i, n, j):
        if bool(gnfa[i][n]):
            in_re = '%s' % gnfa[i][n]
            if '|' in in_re:
                in_re = '(%s)' % in_re
        else:
            in_re = ''

        if bool(gnfa[n][j]):
            nj_re = '%s' % gnfa[n][j]
            if '|' in nj_re:
                nj_re = '(%s)' % nj_re
        else:
            nj_re = ''

        nn_re = ''
        ij_re = ''
        if gnfa[n][n]:
            if (len(gnfa[n][n]) > 1) or ('|' in gnfa[n][n]):
                nn_re = '(%s)*' % gnfa[n][n]
            else:
                nn_re = '%s*' % gnfa[n][n]
        if gnfa[i][j]:
            if (len(gnfa[i][j]) > 1) or ('|' in gnfa[i][j]):
                ij_re = '|(%s)' % gnfa[i][j]
            else:
                ij_re = '|%s' % gnfa[i][j]

        gnfa[i][j] = '%s%s%s%s' % (in_re, nn_re, nj_re, ij_re)

    def _remove_node(gnfa, n):
        global G_debug
        states = list(range(n)) + [len(gnfa) - 1]
        for (i, j) in itertools.product(states, repeat=2):
            if gnfa[i][n] != None != gnfa[n][j]:
                _replace_path(gnfa, i, n, j)
                if G_debug:
                    print('removing node', n)
                    for x in gnfa:
                        print(x)
                    print()

    def _reduce_gnfa(gnfa):
        for n in range(len(gnfa) - 2, -1, -1):
            _remove_node(gnfa, n)
        return '(%s)' % gnfa[-1][-1]

    def dfa_to_regexp(transitions, final):
        """
        Takes DFA's transitions table (transitions) and a set of final
        states (final) and returns a regular expression matching
        that DFA. Starting state is assumed to be 0.
        """
        n = len(transitions)
        if n == 0:
            return None

        # translates transitions table into some sort of
        # adjacency matrix with regexps
        gnfa = [[None] * (n + 1) for i in range(n + 1)]
        gnfa[n][0] = ''
        for i in range(n):
            for j in range(n):
                r = '|'.join(c for c in transitions[i]
                             if transitions[i][c] == j)
                if r:
                    gnfa[i][j] = r
        for q in final:
            gnfa[q][n] = ''
        return _reduce_gnfa(gnfa)

    def dfa_multiples(n):
        """
        Takes integer n and constructs a DFA that can into magic.
        """
        global G_debug
        d = [{} for i in range(n + 2)]
        d[0]['0'] = n + 1
        d[0]['1'] = 2 if n > 1 else 1 # case when n == 1
        d[n + 1]['0'] = d[n + 1]['1'] = n + 1 # reject '^0.*$'
        for i in range(1, n + 1):
            for c in ['0', '1']:
                d[i][c] = (((i - 1) * 2 + int(c, 2)) % n) + 1 # even more magic happens here
        if G_debug:
            for i in range(len(d)):
                print('i=%d%s%s' % (i, ' ' * (5 - len(str(i))), d[i]))
        return d

    return '^(0|' + dfa_to_regexp(dfa_multiples(n), [1]) + ')$'


def test_multiples(n, t=1000, u=1000):
    global G_debug
    print('Testing for n=%d' % n)
    r = multiples(n)

    if G_debug:
        print('n={1:d}\tr=\'{0:s}\''.format(r, n))

    for i in range(t + 1):
        if not test_binary_string(bin(i)[2:], r, n):
            return False
    print('Successfully checked all numbers up to', t)

    for i in range(u):
        s = ''.join(random.choice('01') for j in range(random.randint(0, 63)))
        if not test_binary_string(s, r, n):
            return False
    print('Successfully checked', u, 'random binary strings')

    return True


def test_binary_string(s, r, n):
    match = re.search(r, s)

    if s == '':
        if match:
            print('Error: the regular expression for', n, 'matches the empty string')
            return False
    elif s[0] != '1' and len(s) > 1:
        if match:
            print('Error: the regular expression for', n, 'matches', s)
            return False
    else:
        i = int(s, 2)
        if match:
            if i % n > 0:
                print('Error: the regular expression for', n, 'matches', i)
                return False
        elif i % n == 0:
            print('Error: the regular expression for', n, 'does not match', i)
            return False

    return True


def test_dfa(n, lim=1000, sn=5000, smaxlen=16, verbose_tests=0):
    """
    Custom function for testing DFAs.
    """
    def dfa(transitions, start, final, w):
        q = start
        for c in w:
            q = transitions[q][c]
        if verbose_tests:
            print('dfa: word=\'{1}\', ret={2}'.format(i, w, q in final))
        return q in final

    def make_dfa(transitions, start, final):
        return lambda w: dfa(transitions, start, final, w)

    print('dfa: Testing n={0}'.format(n))
    m = make_dfa(dfa_multiples_old(n), n, [0, n + 1])
    print('dfa: testing {0} numbers'.format(lim))
    for i in range(lim + 1):
        ans = m(bin(i)[2:])
        if ans == True and i % n != 0:
            print('dfa: error: DFA for n={0} matches \'{1}\' while it shouldn\'t'.format(n, bin(i)[2:]))
            return False
        elif ans == False and i % n == 0:
            print('dfa: error: DFA for n={0} doesn\'t match \'{1}\' though it should'.format(n, bin(i)[2:]))
            return False
    print('dfa: success\ndfa: testing {0} random strings'.format(sn))
    for i in range(sn + 1):
        s = ''.join(random.choice('01') for j in range(random.randint(0, smaxlen + 1)))
        ans = m(s)
        if len(s) > 0 and s[0] == '0' and len(s) > 1 and ans != False:
            print('dfa: error: not ignoring non-null string starting w/ 0')
            return False
    return True


if __name__ == '__main__':
    for n in range(1, 8):
        test_multiples(n)
        test_dfa(n)
    for n in range(8, 30):
        test_dfa(n)
    print('success')
